package leetcode.code0403;

public class Solution4 extends Solution403 {

	@Override
	public boolean canCross(int[] stones) {
		int len = stones.length;
		if (stones[1] != 1)
			return false;
		if (len == 2)
			return true;
		int[] ks = new int[len];
		ks[1] = 1;
		boolean[] dp = new boolean[len];
		dp[1] = true;
		//[0,1,3,5,6,8,12,17]
		for (int i = 2; i < len; i++) {
			for (int j = 1; j < i; j++) {
				for (int k = ks[j] - 1; k <= ks[j] + 1; k++) {
					if (stones[i] == stones[j] + k) {
						ks[i] = k;
						dp[i] = true;
					}
				}
			}
		}
		return dp[len - 1];
	}

	public boolean canCross1(int[] stones) {
		if (stones[1] != 1)
			return false;
		if (stones.length == 2)
			return true;
		int[] ks = new int[stones.length];
		ks[0] = 1;
		ks[1] = 1;
		return this.canCross(stones, 2, ks);
	}

	/**
	 * 上一步是k, 现在站在stone上, 能不能跳到最后
	 *
	 * @param stones
	 * @param stone
	 * @param k
	 * @return
	 */
	private boolean canCross(int[] stones, int stone, int[] ks) {
		if (stone == stones.length - 1)
			return true;
		for (int j = 1; j < stone; j++) {
			for (int k = ks[j] - 1; k <= ks[j] + 1; k++) {
				if (stones[stone] == stones[j] + k) {
					ks[stone] = k;
					boolean can = this.canCross(stones, stone + 1, ks);
					if (can)
						return true;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		Solution4 so = new Solution4();
		so.debug1();
		so.debug2();
	}

}
